package org.zxp.datastructure.tree;

import org.junit.Test;

import java.util.Arrays;

/**
 * @program: effectiveJava
 * @description: 二叉查找树
 * @author: X-Pacific zhang
 * @create: 2019-08-02 15:59
 **/
public class TreeSearch {
    //二叉树的根节点
    LinkedTree gen = null;

    /**
     * 构建一颗查找树：node>left  node < right
     */
    private void initLinkedTree(){
        Arrays.asList(33,17,50,13,18,34,58,16,25,51,66,19,27).forEach(o -> {
            insert(gen,o);
        });
    }

    @Test
    public void testSearch(){
        initLinkedTree();
        System.out.println(search(gen,19));
    }

    /**
     * 从t开始查找元素
     * @param t
     * @param data
     * @return
     */
    public LinkedTree search(LinkedTree t,int data){
        if(t == null){
            return null;
        }
        if(data == t.getvInt()){//如果与节点相当返回
            return t;
        }
        if(data > t.getvInt()){//大于当前节点，递归遍历右节点
            t = t.getRight();
        }else{//小于当前节点，递归遍历右节点
            t = t.getLeft();
        }
        return search(t,data);
    }


    @Test
    public void testInsert(){
        initLinkedTree();
        insert(gen,55);
        System.out.println(search(gen,51));
    }


    public void insert(LinkedTree node,int data){
        LinkedTree newTree = new LinkedTree(data);
        if(node == null){
            node = new LinkedTree(data);
            gen = node;
            return;
        }
        LinkedTree t = node;
        if(data > node.getvInt()){
            if (t.getRight() == null) {
                t.setRight(newTree);
                return;
            }else{
                node = t.getRight();
            }
        }else{
            if (t.getLeft() == null) {
                t.setLeft(newTree);
                return;
            }else{
                node = t.getLeft();
            }
        }
        insert(node,data);
    }

    private void sort(LinkedTree t){
        if(t == null)return;
        sort(t.getLeft());
        System.out.println(t.getvInt());
        sort(t.getRight());
    }

    @Test
    public void testSort(){
        initLinkedTree();
        sort(gen);
    }


    /**
     * 从t开始出发，寻找这棵树的最小值
     * @param t
     * @return
     */
    private LinkedTree findMin(LinkedTree t){
        if(t.getLeft() == null){
            return t;
        }
        return findMin(t.getLeft());
    }

    /**
     * 从t开始出发，寻找这棵树的最大值
     * @param t
     * @return
     */
    private LinkedTree findMax(LinkedTree t){
        if(t.getRight() == null){
            return t;
        }
        return findMax(t.getRight());
    }

    @Test
    public void testFindMinMax(){
        initLinkedTree();
        System.out.println(findMin(gen).getvInt());
        System.out.println(findMax(gen).getvInt());
    }




    @Test
    public void testDel(){
        Arrays.asList(33,16,50,13,18,34,58,15,17,25,51,66,19,27,55).forEach(o -> {
            insert(gen,o);
        });
//        System.out.println(search(51));
//        delete(55);
//        System.out.println(search(51));


//        System.out.println(search(16));
//        delete(13);
//        System.out.println(search(16));

        System.out.println(search(gen,19));
        delete(18);
        System.out.println(search(gen,19));
    }




    private void delete(int data){
        //begin search
        LinkedTree p = gen; // p指向要删除的节点，初始化指向根节点
        LinkedTree f = null; // pp记录的是p的父节点
        while (p != null && p.getvInt() != data) {//没找到的条件
            f = p;//在找的过程中记录父节点
            if (data > p.getvInt())
                p = p.getRight();
            else
                p = p.getLeft();
        }
        if (p == null) return; // 没有找到
        //end search

        //两边都不为空，则找到当前节点右子树的最小节点，替换到当前节点，再删除最小节点
        if(p.getLeft() != null && p.getRight() != null) {
            LinkedTree minP = p.getRight();
            LinkedTree minF = p;
            while (minP.getLeft() != null) {
                minF = minP;
                minP = minP.getLeft();
            }
            p.setvInt(minP.getvInt());//替换值即可
            //下面变成删除minP minP一定是没有子节点的
            p = minP;
            f = minF;
        }

        //一边不为空，或者都为空 直接让p的父节点指向 (操作可以兼容上面的操作)
        LinkedTree child = null;
        if(p.getLeft() == null && p.getRight() != null){
            child = p.getRight();
        }
        if(p.getLeft() != null && p.getRight() == null){
            child = p.getLeft();
        }
        if(f.getRight() == p){
            f.setRight(child);
        }else if(f.getLeft() == p){
            f.setLeft(child);
        }else{
            System.out.println("error");
        }
    }

}
